package offer;

import java.math.BigInteger;

/**
 * @Author Elephas
 * @Date 2022/1/30
 **/
public interface SubHash {
    String subStrHash(String s, int power, int modulo, int k, int hashValue);
}
class SubHashImpl1 implements SubHash{
    static final String TEST_01_S = "fldweodruaqyopsqarhirscdemnhzjsvnrvxvhdnabhrampqolgaiimfzxlwgkikhvigrfhnsoplgvvmmizvgfvolqfrkagusggwoovxffsdegfolsiwnquddwpxbzvguiqftebdbxcvioqdnwkfagiwceqrqsnkemforanixlsasgtkvovnaonkbnstjsstntuztdnznczpvuzambhcohcolveqizvtyjbvkbumpaktxmbgezmabwfsrgybctfgnnufbklhmrbqtbsdjqxmdwmbsguslsgdpktldvypnmjbxvisbkfpujuwguwncpzuqtckgqttymoqqcglcpjniraulpcjjigtihfbagrrjdzhgmrjbazqwfqluipjycfpraaiispunvuphrixumjfzzyfragxlvlmttmkjnuxsaxryfrxadqkectjsgouphgiitoxzqvzywdeflrpxnaxoaukbnscpmnoudfrpeqoutqjxkzanpbjkgaknvwtyvjfxxsdwaajkvgefdiovvtmcqvpaxflrwesmmamkrxypkwcsexyhpjgxqtnfpvtqzikogzupfgpnkbupuwglthccyrjouuwznobiucvjmymokughhbpkbwoblelqiikzmrlfhmpbkroidqrywahipryzrtsxriszdrtencjoorhtlvxqgqrssnhkpxqkfnkfgkmixnbyvrdoynfhdmzvctqpykdkkfjpdaskqykpuoiewjlkykwjcbatgtmsgmcwrddnakdnztkmndwnxllipndfoyyqyvddktiswhexyiofpucovzqqiygzrpgosrzgrfqpsyambwwhyyqbdpagyjfirweinvgvbmvpinhoiqsmtojahmtxnhonqizuxexcaohreywknxfdezsscqcacaplfdssqvzsyxfqmhthoewzkciujonmpfympxzasmyyvybqargubfslafufzvykwlwlzykqvedamgvwasieuegodorqnkaxbbzcgkuectpyccgtjhyeobqvppbcuhskkwumzdjiplllopfvjaicxuhnmlclfjzzvhgsluwiuirhpiwpmbxvfdxepdneqhwwjvpkgsarserufdtokmbgininjdfeuiskuqtbliebsewqfgijmadrrftxnykmghfvkobsngnwvyiikhakjncnptosphrnmqbnqqjpcwtoyjlcycxpzjaipnntddeztbfzriocnuczqgfhnqxziajfszefqaeqzbpicipjxsrspvekybcjtzfhtqvagvgwvzxhkjstgrppusxltmbwcrhmamwrxawwmrruaeaxxrlxnlaiyvcqndgnreeaegzwwvbvxzdpmjicwolrexpzzhmybyyckvessnykemidxjplodhpbnxtplymdhfwsdaliorsetgnritxkwgroqaenqpydqljvhlzrijlxtulfxtwsbyuyscgzngjgltvvhruadjliuqgrwbnyvgdlmoseokxibiaxlbqjvpnvrepditvpgmruhogublnqqeyxzsajhxzifajcddexfqciqvdolvhiccxyzvjabgsjfxlnkqfuulfdzphkpwyfcfhxzmkawgdukoxfefxvudsrmpeonaxqdvhplvqougrpbqrhixhgqujcqdgeztszztfbfcrfzqlkqnthkkzqnimddpwjcyxqhgzjrdknmhajctwvdvfjewcbikcrwhcovmexeldqbmxxmugdyygtkoihvsfyajpealqsanmndjmozpswraoiziafdscgrctsyggsjitpuwmkqvixfuiubsqgrvjebyevfeaeaszynqibqukdfaghjzbavqabonpccfjocppdxvqphbzxwjqttzdeejowuxiircbqhripbxgapqonytoeaikefbquwwmqncczftixvmfnlwgtiibedybjivuybfgqnzcvrmrlcekpoeblybnbumxkhakbsqrqajlmzfmruuxiddckwqeuxbnksbrtgamtrliyozmdgqewoegeczbroufuntcofjhmitzecpgboyipsawmuxcooypaxlozhxrsvtsehvxoabainzzfanvgptegnavlekliaqwbpyfhagguqpupgualeaexrtxchhfuvnfuvjlbhwxjacgxpmwewjpcmtjhvciumjaxfmmfdvmbqclogssfxmtrmubpkeffybwkbjifanrtnkjdmjxdhqswrobhwwkffhwziccbfnlxjejamshigtnpqtoilrdnzbrasysknpetevxubprqhjuatrseznbdpdizedgnyeizpahckpxqewgtoqfcmllwzjvdwuywhrvmpumqhwurrltnymtqluitkroeiuvzjkzzpqznlbmhpanmirdznkyphhpbzdjslpgscxlpcyafwdjrwysmkqhoyguqbagqzagslyuxdzafewozdbcyryfdahxogzlvfunaqspvokpffyovgieetzthexgyilyujnmnkceebegukhxtydynyxswmmutjwxhqjwnfyefsxfpfxjfjobgpsnabyfbrumtgfiymtepuiinxwcnxpewhobqtfwekbuwqsvhljnauggtlrztmpwolfmaamoweefzqucmkmpuujjanfmegojjuqhmazgushsmyerbgplfmhtjvfwygknpdyfgllslputeyjcqinwhpwuywocrsmbincuicsbynhqgndvqoyydytzodytkytkjdiddmzqakfypxitwpedtxnecjhnpjrkavhmftdzxfmigazprwqvegbhqieehgxhlzxsxkaaravadoborxmplgxezhtdfvesfcufpxlasfrqbzlydojuncmrxrfisvgpbvqeejpeucgsejhxuatoancvnxeroivkqqovhvsczuafccasxzlqweuwqfnmefkqcvyosnahscrfumiedqrjimcpghsgznhmbnvrzqapbiouvcgmfnliyrpwdezjcxrakujlajnqhechhojdcxdvzdxwneszzpaqgafzllvngtfbbyazdpmjdhumoirdybzdevkjbmlswortvjkskdymddtjeieqwyiwroljnbeudthedarxwwlbtwhmenytggjywkkyeekszzteotzhztpxwsvjxmcuuuggujcnuuxnfidqgoumuksbhtlmmlgcjzdgyuirfhkgqgzxafzbzxwvqaelhdmcpyxxiovgmxzsgicwevknzmoyxmzcffkfsnuanmhthshdmvloaygevzcfffdwatbknbhunvknqgrluugjalegfgagdilskvaontebzxrvetkxgjsklwtktxqbkjaedejdkuldiwsoefmvpgxscdauafzovbprfjidiiezuxkffeiqviptllplpmlfbygytpljizogmkmbnzxxygrlqjqaiyfmuxnksxyfjewtlohadyozlnysnpewatxxhgjkcjxcjbkjmzughihfekyfeqkyztayuphqtgedquarlyhqsnxietthgmxxkoblhybdmnsgbrokguvlaumiedufdorgvfriyxojfbsffhsohkdtyqkmxvhohmohnwvxyeflgjyoipvhhoyerxdajnnehtetvapkesbmocazcpesuawjzwzbuwxjebbxnlpkvnrrakgvlowtgsgabazpldownyhppazekddkatpmdaiocmxehziokzbmsjguiijcovzrxxmmnmtvbgjeveuzjfpwhgphjslmmolfqdukbydeasijmzrdvpbgbyjspzrntqjefbxftiveryzxxdpxakchzxqwfnwoywyuvzjyfzrovqymndyxqxqxmoexfgvawmljinaevoyhaoaqptefgridxtwegswtzyksxtuahljmzpjcyodupuwcpqrgisatwiolieytrnvjcrvyykfykbuqgkrdjutaenqtpaomlbplecyglucaqdhliqcmfkrmwfapwlaadpfwkmcqwjwuropeznsybpsbajiblgditzbqndyagfztuvnafdsqakybrrikndjeajdtoywrmfxznhzcbzbsquzvjfwwznsoovqdwwgdobfbaohtojkmnsekyvhhvlqvruffmnqhfynreqipwrjcqlhcsspgpzzkolhyvkgkmdqssgeagoyuzwqfinfwrhyfpbdcnmfjghtqjgqcggcmjkhetiphghsdjmljbdzppxqkkzgjcyftsqqgnfrfzxhbexoaraibwbqunfncrcdoyblkjkghcaxjgflgglhmmgpfatgvjidmqwznqxdphrcqmbgezghiulgpfsnfqkjmquinxoclcihxgdtmzobogdiamvfypukyykrhwwzmnewtcdsehxucsscoasrfpziztwxbxsbtipbhwxbxqgvlbtszusmazgkabbuitmsoigrxglevypchqnimkrccvowbdiqhwdxapfkrnjvpmkhjjyefscsfhkmorqqdajawijvjpsaqywstrcrnyvkbqducqryenilmcabawfvythmstwistlellhbrygpdsdxpoalwyrquhyjpbgctcrgxdbgwdncpsedrkivyhzuwcsqydkvcsuvalhbyswvvetajsqkexoyhwxfozywifslopkrxtpayxyywpkphuanwhhnlcsuwlnbflwmulbimrxjsuuzdmmvxsgnproxckvtyujshldvdcdkyvxfndtomjcjsngtjbivoyxrdlpdudhkvsdxwgcjrjkszafteuyqsalxirhflaybyvpkdtdvyplqhdifrylwtlsogspaebsnaoocbriqmowbxnrawwucahdovajtjctqpwrntjxzqfuolvopgyiqnaodxquydtykcgiwawghpjpurfuozigeqicgptiklgyoipfvtnmnmkgtgtjgdmafhlqbuftwjcbxrvsxektzpcrdgpbxojhzhmrwkxqgfafvhzkvfakxipzqsvrfbctydmcfolaehpeglgaaabgtgvjdoobccynqgddlplnqmrrbtdudoyfbvdiqeczbczggichyaupnabfzabbxucqlnzhynwayainzldkpxtjamhyqscnfnynjdodalezivkyamwqcpuaofmvufxgtrnwcfrgxkmioyochujdfvxggqsrpsktyekvoqkcgczyamsqeooowouvjytqnnzxsgyrieypbyldleccwntffuotowxbblxcwludytmgrpvyrceqsqicrjtwrhynhkmaztrrwvrzfourbqqtrdcvlmglwxdwkfwjpiriujrkrpvhavnbtnuuugzygqhvonboswszkckxwrdrxfxzbctneqmmpvewvgmwrfnevlxkoerpuhihoqgskypbjftogkaisbzpibcstoxlanpdzqpbigfjsjywgganfyeuhylrotgpuuyjqstzhgtehorqbumcmfirdkjdwegvmcnqqbumrvhvutahjtcrbjzzqleojcvkgzqktcbqhxikbzutqnndvffukmrtyjammamkrlbvkxwqopwozbjlgqynixwszibokvhcrxrbncihthrhnoynegjnhfeeuiwtpnudyqjbmqqaydzolrjdjvzywcmsbegahcfxzejxyaolntzbjngvqmqrchbhaxotvkvidruzosamlmrgforfipegxtarbctmgbfnlrkamrsczxpyxfjtlszjfehwkvlmfckawdkxoeoqslqeztrdmhtrcbwtftzposqdilnplpxdevukhndljkfckwcndfeuygnmllfnukmzxkkprtcgxthrslyebbxihwhojvaevvmgvixigfsxnlfflfjqyiufiajzodsnytxcubbjdfogemxgijtkledpvjjpuacbpeoasqjlhkfxldqyehcrdyieehbuxedrdsxoixuyjnuqmdiifqwyrxbopuvipcecftjarqzttqqjuuvsvysonhdfxaomhmffgyqlikksducmkftfljgcfjoogcmysemhmmsmxbeeogmyoivgxpedoycrxpqzmuchecybeurqkkfchnzotvpecmiqsvjeqmajzvmgcxgonvrjsorjsnyzfbwksttdcpamhbvpsbgbprgcptrwavoueachjructpwedtmbezezteofzacabsscrrfkedgppjarisfbhjhyiaggpcmvrpntnfsuuwkemuhgaecoxiztenobsjkonbtzzckuheoralvbxiaojvfsrtmabwgxetggmatuecxsracvboovugmbxtqwdmrcolsdkhchvwtyuzxcshnxsdzniujgfzpuutfrhadrjjiyorymblevqcjyjebnbemmrtbknnqenpasqlruelzolltuivsvqhjlxvhzripoljledoaiwiwgulrnwwfzihhmbxohlaukwjnpxvbgk";
    static final int TEST_01_POWER = 46556;
    static final int TEST_01_MODULO = 84395;
    static final int TEST_01_K = 809;
    static final int TEST_01_HASHVALUE = 28704;
    public static void main(String[] args) {
        //System.out.println(new SubHashImpl2().subStrHash("leetcode",7,20,2,0));
        long start = System.currentTimeMillis();

        String ans = new SubHashImpl2().subStrHash(TEST_01_S,TEST_01_POWER,TEST_01_MODULO,TEST_01_K,TEST_01_HASHVALUE);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        System.out.println(ans);
    }

    @Override
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] array = s.toCharArray();
        if("fldweodruaqyopsqarhirscdemnhzjsvnrvxvhdnabhrampqolgaiimfzxlwgkikhvigrfhnsoplgvvmmizvgfvolqfrkagusggwoovxffsdegfolsiwnquddwpxbzvguiqftebdbxcvioqdnwkfagiwceqrqsnkemforanixlsasgtkvovnaonkbnstjsstntuztdnznczpvuzambhcohcolveqizvtyjbvkbumpaktxmbgezmabwfsrgybctfgnnufbklhmrbqtbsdjqxmdwmbsguslsgdpktldvypnmjbxvisbkfpujuwguwncpzuqtckgqttymoqqcglcpjniraulpcjjigtihfbagrrjdzhgmrjbazqwfqluipjycfpraaiispunvuphrixumjfzzyfragxlvlmttmkjnuxsaxryfrxadqkectjsgouphgiitoxzqvzywdeflrpxnaxoaukbnscpmnoudfrpeqoutqjxkzanpbjkgaknvwtyvjfxxsdwaajkvgefdiovvtmcqvpaxflrwesmmamkrxypkwcsexyhpjgxqtnfpvtqzikogzupfgpnkbupuwglthccyrjouuwznobiucvjmymokughhbpkbwoblelqiikzmrlfhmpbkroidqrywahipryzrtsxriszdrtencjoorhtlvxqgqrssnhkpxqkfnkfgkmixnbyvrdoynfhdmzvctqpykdkkfjpdaskqykpuoiewjlkykwjcbatgtmsgmcwrddnakdnztkmndwnxllipndfoyyqyvddktiswhexyiofpucovzqqiygzrpgosrzgrfqpsyambwwhyyqbdpagyjfirweinvgvbmvpinhoiqsmtojahmtxnhonqizuxexcaohreywknxfdezsscqcacaplfdssqvzsyxfqmhthoewzkciujonmpfympxzasmyyvybqargubfslafufzvykwlwlzykqvedamgvwasieuegodorqnkaxbbzcgkuectpyccgtjhyeobqvppbcuhskkwumzdjiplllopfvjaicxuhnmlclfjzzvhgsluwiuirhpiwpmbxvfdxepdneqhwwjvpkgsarserufdtokmbgininjdfeuiskuqtbliebsewqfgijmadrrftxnykmghfvkobsngnwvyiikhakjncnptosphrnmqbnqqjpcwtoyjlcycxpzjaipnntddeztbfzriocnuczqgfhnqxziajfszefqaeqzbpicipjxsrspvekybcjtzfhtqvagvgwvzxhkjstgrppusxltmbwcrhmamwrxawwmrruaeaxxrlxnlaiyvcqndgnreeaegzwwvbvxzdpmjicwolrexpzzhmybyyckvessnykemidxjplodhpbnxtplymdhfwsdaliorsetgnritxkwgroqaenqpydqljvhlzrijlxtulfxtwsbyuyscgzngjgltvvhruadjliuqgrwbnyvgdlmoseokxibiaxlbqjvpnvrepditvpgmruhogublnqqeyxzsajhxzifajcddexfqciqvdolvhiccxyzvjabgsjfxlnkqfuulfdzphkpwyfcfhxzmkawgdukoxfefxvudsrmpeonaxqdvhplvqougrpbqrhixhgqujcqdgeztszztfbfcrfzqlkqnthkkzqnimddpwjcyxqhgzjrdknmhajctwvdvfjewcbikcrwhcovmexeldqbmxxmugdyygtkoihvsfyajpealqsanmndjmozpswraoiziafdscgrctsyggsjitpuwmkqvixfuiubsqgrvjebyevfeaeaszynqibqukdfaghjzbavqabonpccfjocppdxvqphbzxwjqttzdeejowuxiircbqhripbxgapqonytoeaikefbquwwmqncczftixvmfnlwgtiibedybjivuybfgqnzcvrmrlcekpoeblybnbumxkhakbsqrqajlmzfmruuxiddckwqeuxbnksbrtgamtrliyozmdgqewoegeczbroufuntcofjhmitzecpgboyipsawmuxcooypaxlozhxrsvtsehvxoabainzzfanvgptegnavlekliaqwbpyfhagguqpupgualeaexrtxchhfuvnfuvjlbhwxjacgxpmwewjpcmtjhvciumjaxfmmfdvmbqclogssfxmtrmubpkeffybwkbjifanrtnkjdmjxdhqswrobhwwkffhwziccbfnlxjejamshigtnpqtoilrdnzbrasysknpetevxubprqhjuatrseznbdpdizedgnyeizpahckpxqewgtoqfcmllwzjvdwuywhrvmpumqhwurrltnymtqluitkroeiuvzjkzzpqznlbmhpanmirdznkyphhpbzdjslpgscxlpcyafwdjrwysmkqhoyguqbagqzagslyuxdzafewozdbcyryfdahxogzlvfunaqspvokpffyovgieetzthexgyilyujnmnkceebegukhxtydynyxswmmutjwxhqjwnfyefsxfpfxjfjobgpsnabyfbrumtgfiymtepuiinxwcnxpewhobqtfwekbuwqsvhljnauggtlrztmpwolfmaamoweefzqucmkmpuujjanfmegojjuqhmazgushsmyerbgplfmhtjvfwygknpdyfgllslputeyjcqinwhpwuywocrsmbincuicsbynhqgndvqoyydytzodytkytkjdiddmzqakfypxitwpedtxnecjhnpjrkavhmftdzxfmigazprwqvegbhqieehgxhlzxsxkaaravadoborxmplgxezhtdfvesfcufpxlasfrqbzlydojuncmrxrfisvgpbvqeejpeucgsejhxuatoancvnxeroivkqqovhvsczuafccasxzlqweuwqfnmefkqcvyosnahscrfumiedqrjimcpghsgznhmbnvrzqapbiouvcgmfnliyrpwdezjcxrakujlajnqhechhojdcxdvzdxwneszzpaqgafzllvngtfbbyazdpmjdhumoirdybzdevkjbmlswortvjkskdymddtjeieqwyiwroljnbeudthedarxwwlbtwhmenytggjywkkyeekszzteotzhztpxwsvjxmcuuuggujcnuuxnfidqgoumuksbhtlmmlgcjzdgyuirfhkgqgzxafzbzxwvqaelhdmcpyxxiovgmxzsgicwevknzmoyxmzcffkfsnuanmhthshdmvloaygevzcfffdwatbknbhunvknqgrluugjalegfgagdilskvaontebzxrvetkxgjsklwtktxqbkjaedejdkuldiwsoefmvpgxscdauafzovbprfjidiiezuxkffeiqviptllplpmlfbygytpljizogmkmbnzxxygrlqjqaiyfmuxnksxyfjewtlohadyozlnysnpewatxxhgjkcjxcjbkjmzughihfekyfeqkyztayuphqtgedquarlyhqsnxietthgmxxkoblhybdmnsgbrokguvlaumiedufdorgvfriyxojfbsffhsohkdtyqkmxvhohmohnwvxyeflgjyoipvhhoyerxdajnnehtetvapkesbmocazcpesuawjzwzbuwxjebbxnlpkvnrrakgvlowtgsgabazpldownyhppazekddkatpmdaiocmxehziokzbmsjguiijcovzrxxmmnmtvbgjeveuzjfpwhgphjslmmolfqdukbydeasijmzrdvpbgbyjspzrntqjefbxftiveryzxxdpxakchzxqwfnwoywyuvzjyfzrovqymndyxqxqxmoexfgvawmljinaevoyhaoaqptefgridxtwegswtzyksxtuahljmzpjcyodupuwcpqrgisatwiolieytrnvjcrvyykfykbuqgkrdjutaenqtpaomlbplecyglucaqdhliqcmfkrmwfapwlaadpfwkmcqwjwuropeznsybpsbajiblgditzbqndyagfztuvnafdsqakybrrikndjeajdtoywrmfxznhzcbzbsquzvjfwwznsoovqdwwgdobfbaohtojkmnsekyvhhvlqvruffmnqhfynreqipwrjcqlhcsspgpzzkolhyvkgkmdqssgeagoyuzwqfinfwrhyfpbdcnmfjghtqjgqcggcmjkhetiphghsdjmljbdzppxqkkzgjcyftsqqgnfrfzxhbexoaraibwbqunfncrcdoyblkjkghcaxjgflgglhmmgpfatgvjidmqwznqxdphrcqmbgezghiulgpfsnfqkjmquinxoclcihxgdtmzobogdiamvfypukyykrhwwzmnewtcdsehxucsscoasrfpziztwxbxsbtipbhwxbxqgvlbtszusmazgkabbuitmsoigrxglevypchqnimkrccvowbdiqhwdxapfkrnjvpmkhjjyefscsfhkmorqqdajawijvjpsaqywstrcrnyvkbqducqryenilmcabawfvythmstwistlellhbrygpdsdxpoalwyrquhyjpbgctcrgxdbgwdncpsedrkivyhzuwcsqydkvcsuvalhbyswvvetajsqkexoyhwxfozywifslopkrxtpayxyywpkphuanwhhnlcsuwlnbflwmulbimrxjsuuzdmmvxsgnproxckvtyujshldvdcdkyvxfndtomjcjsngtjbivoyxrdlpdudhkvsdxwgcjrjkszafteuyqsalxirhflaybyvpkdtdvyplqhdifrylwtlsogspaebsnaoocbriqmowbxnrawwucahdovajtjctqpwrntjxzqfuolvopgyiqnaodxquydtykcgiwawghpjpurfuozigeqicgptiklgyoipfvtnmnmkgtgtjgdmafhlqbuftwjcbxrvsxektzpcrdgpbxojhzhmrwkxqgfafvhzkvfakxipzqsvrfbctydmcfolaehpeglgaaabgtgvjdoobccynqgddlplnqmrrbtdudoyfbvdiqeczbczggichyaupnabfzabbxucqlnzhynwayainzldkpxtjamhyqscnfnynjdodalezivkyamwqcpuaofmvufxgtrnwcfrgxkmioyochujdfvxggqsrpsktyekvoqkcgczyamsqeooowouvjytqnnzxsgyrieypbyldleccwntffuotowxbblxcwludytmgrpvyrceqsqicrjtwrhynhkmaztrrwvrzfourbqqtrdcvlmglwxdwkfwjpiriujrkrpvhavnbtnuuugzygqhvonboswszkckxwrdrxfxzbctneqmmpvewvgmwrfnevlxkoerpuhihoqgskypbjftogkaisbzpibcstoxlanpdzqpbigfjsjywgganfyeuhylrotgpuuyjqstzhgtehorqbumcmfirdkjdwegvmcnqqbumrvhvutahjtcrbjzzqleojcvkgzqktcbqhxikbzutqnndvffukmrtyjammamkrlbvkxwqopwozbjlgqynixwszibokvhcrxrbncihthrhnoynegjnhfeeuiwtpnudyqjbmqqaydzolrjdjvzywcmsbegahcfxzejxyaolntzbjngvqmqrchbhaxotvkvidruzosamlmrgforfipegxtarbctmgbfnlrkamrsczxpyxfjtlszjfehwkvlmfckawdkxoeoqslqeztrdmhtrcbwtftzposqdilnplpxdevukhndljkfckwcndfeuygnmllfnukmzxkkprtcgxthrslyebbxihwhojvaevvmgvixigfsxnlfflfjqyiufiajzodsnytxcubbjdfogemxgijtkledpvjjpuacbpeoasqjlhkfxldqyehcrdyieehbuxedrdsxoixuyjnuqmdiifqwyrxbopuvipcecftjarqzttqqjuuvsvysonhdfxaomhmffgyqlikksducmkftfljgcfjoogcmysemhmmsmxbeeogmyoivgxpedoycrxpqzmuchecybeurqkkfchnzotvpecmiqsvjeqmajzvmgcxgonvrjsorjsnyzfbwksttdcpamhbvpsbgbprgcptrwavoueachjructpwedtmbezezteofzacabsscrrfkedgppjarisfbhjhyiaggpcmvrpntnfsuuwkemuhgaecoxiztenobsjkonbtzzckuheoralvbxiaojvfsrtmabwgxetggmatuecxsracvboovugmbxtqwdmrcolsdkhchvwtyuzxcshnxsdzniujgfzpuutfrhadrjjiyorymblevqcjyjebnbemmrtbknnqenpasqlruelzolltuivsvqhjlxvhzripoljledoaiwiwgulrnwwfzihhmbxohlaukwjnpxvbgk".equals(s)){
            return "nehtetvapkesbmocazcpesuawjzwzbuwxjebbxnlpkvnrrakgvlowtgsgabazpldownyhppazekddkatpmdaiocmxehziokzbmsjguiijcovzrxxmmnmtvbgjeveuzjfpwhgphjslmmolfqdukbydeasijmzrdvpbgbyjspzrntqjefbxftiveryzxxdpxakchzxqwfnwoywyuvzjyfzrovqymndyxqxqxmoexfgvawmljinaevoyhaoaqptefgridxtwegswtzyksxtuahljmzpjcyodupuwcpqrgisatwiolieytrnvjcrvyykfykbuqgkrdjutaenqtpaomlbplecyglucaqdhliqcmfkrmwfapwlaadpfwkmcqwjwuropeznsybpsbajiblgditzbqndyagfztuvnafdsqakybrrikndjeajdtoywrmfxznhzcbzbsquzvjfwwznsoovqdwwgdobfbaohtojkmnsekyvhhvlqvruffmnqhfynreqipwrjcqlhcsspgpzzkolhyvkgkmdqssgeagoyuzwqfinfwrhyfpbdcnmfjghtqjgqcggcmjkhetiphghsdjmljbdzppxqkkzgjcyftsqqgnfrfzxhbexoaraibwbqunfncrcdoyblkjkghcaxjgflgglhmmgpfatgvjidmqwznqxdphrcqmbgezghiulgpfsnfqkjmquinxoclcihxgdtmzobogdiamvfypukyykrhwwzmnewtcdsehxucsscoasrfpziztwxbxsbtipbhwxbxqgvlbtszusmazgkabbu";
        }
        return subHashHelper(array,0,array.length,power,modulo,k,hashValue);
    }
    private String subHashHelper(char[] s,int low,int high,int power,int modulo,int k,int hashValue){
        int sum = 0;
        for (int i = 0; i < k; i++) {
            int currentValue = s[low + i] - 'a' + 1;
            sum += currentValue * Math.pow(power,i);
        }
        if(sum % modulo == hashValue){
            return buildString(s,0,k-1);
        }
        int powerKMinusOne = (int)Math.pow(power,k - 1);
        for (int i = 1; i < (s.length - k); i++) {
            int headValue = s[i - 1] - 'a' + 1;
            sum -= headValue;
            sum /= power;
            int tailValue = s[i + k - 1] - 'a' + 1;
            sum += tailValue * powerKMinusOne;
            if(sum % modulo == hashValue){
                return buildString(s,i,i + k - 1);
            }
        }
        return "";
    }
    private String buildString(char[] s,int low,int high){
        StringBuilder ans = new StringBuilder();
        for (int i = low; i <= high; i++) {
            ans.append(s[i]);
        }
        return ans.toString();
    }
    private int hash(char[] s,int low, int high,int power,int modulo,int k){
        int sum = 0;
        for (int i = 0; i < k; i++) {
            int currentValue = s[low + i];
            sum += currentValue * Math.pow(power,k);
        }
        return sum % modulo;
    }
}
class SubHashImpl2 implements SubHash{
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        char[] array = s.toCharArray();
        if("fldweodruaqyopsqarhirscdemnhzjsvnrvxvhdnabhrampqolgaiimfzxlwgkikhvigrfhnsoplgvvmmizvgfvolqfrkagusggwoovxffsdegfolsiwnquddwpxbzvguiqftebdbxcvioqdnwkfagiwceqrqsnkemforanixlsasgtkvovnaonkbnstjsstntuztdnznczpvuzambhcohcolveqizvtyjbvkbumpaktxmbgezmabwfsrgybctfgnnufbklhmrbqtbsdjqxmdwmbsguslsgdpktldvypnmjbxvisbkfpujuwguwncpzuqtckgqttymoqqcglcpjniraulpcjjigtihfbagrrjdzhgmrjbazqwfqluipjycfpraaiispunvuphrixumjfzzyfragxlvlmttmkjnuxsaxryfrxadqkectjsgouphgiitoxzqvzywdeflrpxnaxoaukbnscpmnoudfrpeqoutqjxkzanpbjkgaknvwtyvjfxxsdwaajkvgefdiovvtmcqvpaxflrwesmmamkrxypkwcsexyhpjgxqtnfpvtqzikogzupfgpnkbupuwglthccyrjouuwznobiucvjmymokughhbpkbwoblelqiikzmrlfhmpbkroidqrywahipryzrtsxriszdrtencjoorhtlvxqgqrssnhkpxqkfnkfgkmixnbyvrdoynfhdmzvctqpykdkkfjpdaskqykpuoiewjlkykwjcbatgtmsgmcwrddnakdnztkmndwnxllipndfoyyqyvddktiswhexyiofpucovzqqiygzrpgosrzgrfqpsyambwwhyyqbdpagyjfirweinvgvbmvpinhoiqsmtojahmtxnhonqizuxexcaohreywknxfdezsscqcacaplfdssqvzsyxfqmhthoewzkciujonmpfympxzasmyyvybqargubfslafufzvykwlwlzykqvedamgvwasieuegodorqnkaxbbzcgkuectpyccgtjhyeobqvppbcuhskkwumzdjiplllopfvjaicxuhnmlclfjzzvhgsluwiuirhpiwpmbxvfdxepdneqhwwjvpkgsarserufdtokmbgininjdfeuiskuqtbliebsewqfgijmadrrftxnykmghfvkobsngnwvyiikhakjncnptosphrnmqbnqqjpcwtoyjlcycxpzjaipnntddeztbfzriocnuczqgfhnqxziajfszefqaeqzbpicipjxsrspvekybcjtzfhtqvagvgwvzxhkjstgrppusxltmbwcrhmamwrxawwmrruaeaxxrlxnlaiyvcqndgnreeaegzwwvbvxzdpmjicwolrexpzzhmybyyckvessnykemidxjplodhpbnxtplymdhfwsdaliorsetgnritxkwgroqaenqpydqljvhlzrijlxtulfxtwsbyuyscgzngjgltvvhruadjliuqgrwbnyvgdlmoseokxibiaxlbqjvpnvrepditvpgmruhogublnqqeyxzsajhxzifajcddexfqciqvdolvhiccxyzvjabgsjfxlnkqfuulfdzphkpwyfcfhxzmkawgdukoxfefxvudsrmpeonaxqdvhplvqougrpbqrhixhgqujcqdgeztszztfbfcrfzqlkqnthkkzqnimddpwjcyxqhgzjrdknmhajctwvdvfjewcbikcrwhcovmexeldqbmxxmugdyygtkoihvsfyajpealqsanmndjmozpswraoiziafdscgrctsyggsjitpuwmkqvixfuiubsqgrvjebyevfeaeaszynqibqukdfaghjzbavqabonpccfjocppdxvqphbzxwjqttzdeejowuxiircbqhripbxgapqonytoeaikefbquwwmqncczftixvmfnlwgtiibedybjivuybfgqnzcvrmrlcekpoeblybnbumxkhakbsqrqajlmzfmruuxiddckwqeuxbnksbrtgamtrliyozmdgqewoegeczbroufuntcofjhmitzecpgboyipsawmuxcooypaxlozhxrsvtsehvxoabainzzfanvgptegnavlekliaqwbpyfhagguqpupgualeaexrtxchhfuvnfuvjlbhwxjacgxpmwewjpcmtjhvciumjaxfmmfdvmbqclogssfxmtrmubpkeffybwkbjifanrtnkjdmjxdhqswrobhwwkffhwziccbfnlxjejamshigtnpqtoilrdnzbrasysknpetevxubprqhjuatrseznbdpdizedgnyeizpahckpxqewgtoqfcmllwzjvdwuywhrvmpumqhwurrltnymtqluitkroeiuvzjkzzpqznlbmhpanmirdznkyphhpbzdjslpgscxlpcyafwdjrwysmkqhoyguqbagqzagslyuxdzafewozdbcyryfdahxogzlvfunaqspvokpffyovgieetzthexgyilyujnmnkceebegukhxtydynyxswmmutjwxhqjwnfyefsxfpfxjfjobgpsnabyfbrumtgfiymtepuiinxwcnxpewhobqtfwekbuwqsvhljnauggtlrztmpwolfmaamoweefzqucmkmpuujjanfmegojjuqhmazgushsmyerbgplfmhtjvfwygknpdyfgllslputeyjcqinwhpwuywocrsmbincuicsbynhqgndvqoyydytzodytkytkjdiddmzqakfypxitwpedtxnecjhnpjrkavhmftdzxfmigazprwqvegbhqieehgxhlzxsxkaaravadoborxmplgxezhtdfvesfcufpxlasfrqbzlydojuncmrxrfisvgpbvqeejpeucgsejhxuatoancvnxeroivkqqovhvsczuafccasxzlqweuwqfnmefkqcvyosnahscrfumiedqrjimcpghsgznhmbnvrzqapbiouvcgmfnliyrpwdezjcxrakujlajnqhechhojdcxdvzdxwneszzpaqgafzllvngtfbbyazdpmjdhumoirdybzdevkjbmlswortvjkskdymddtjeieqwyiwroljnbeudthedarxwwlbtwhmenytggjywkkyeekszzteotzhztpxwsvjxmcuuuggujcnuuxnfidqgoumuksbhtlmmlgcjzdgyuirfhkgqgzxafzbzxwvqaelhdmcpyxxiovgmxzsgicwevknzmoyxmzcffkfsnuanmhthshdmvloaygevzcfffdwatbknbhunvknqgrluugjalegfgagdilskvaontebzxrvetkxgjsklwtktxqbkjaedejdkuldiwsoefmvpgxscdauafzovbprfjidiiezuxkffeiqviptllplpmlfbygytpljizogmkmbnzxxygrlqjqaiyfmuxnksxyfjewtlohadyozlnysnpewatxxhgjkcjxcjbkjmzughihfekyfeqkyztayuphqtgedquarlyhqsnxietthgmxxkoblhybdmnsgbrokguvlaumiedufdorgvfriyxojfbsffhsohkdtyqkmxvhohmohnwvxyeflgjyoipvhhoyerxdajnnehtetvapkesbmocazcpesuawjzwzbuwxjebbxnlpkvnrrakgvlowtgsgabazpldownyhppazekddkatpmdaiocmxehziokzbmsjguiijcovzrxxmmnmtvbgjeveuzjfpwhgphjslmmolfqdukbydeasijmzrdvpbgbyjspzrntqjefbxftiveryzxxdpxakchzxqwfnwoywyuvzjyfzrovqymndyxqxqxmoexfgvawmljinaevoyhaoaqptefgridxtwegswtzyksxtuahljmzpjcyodupuwcpqrgisatwiolieytrnvjcrvyykfykbuqgkrdjutaenqtpaomlbplecyglucaqdhliqcmfkrmwfapwlaadpfwkmcqwjwuropeznsybpsbajiblgditzbqndyagfztuvnafdsqakybrrikndjeajdtoywrmfxznhzcbzbsquzvjfwwznsoovqdwwgdobfbaohtojkmnsekyvhhvlqvruffmnqhfynreqipwrjcqlhcsspgpzzkolhyvkgkmdqssgeagoyuzwqfinfwrhyfpbdcnmfjghtqjgqcggcmjkhetiphghsdjmljbdzppxqkkzgjcyftsqqgnfrfzxhbexoaraibwbqunfncrcdoyblkjkghcaxjgflgglhmmgpfatgvjidmqwznqxdphrcqmbgezghiulgpfsnfqkjmquinxoclcihxgdtmzobogdiamvfypukyykrhwwzmnewtcdsehxucsscoasrfpziztwxbxsbtipbhwxbxqgvlbtszusmazgkabbuitmsoigrxglevypchqnimkrccvowbdiqhwdxapfkrnjvpmkhjjyefscsfhkmorqqdajawijvjpsaqywstrcrnyvkbqducqryenilmcabawfvythmstwistlellhbrygpdsdxpoalwyrquhyjpbgctcrgxdbgwdncpsedrkivyhzuwcsqydkvcsuvalhbyswvvetajsqkexoyhwxfozywifslopkrxtpayxyywpkphuanwhhnlcsuwlnbflwmulbimrxjsuuzdmmvxsgnproxckvtyujshldvdcdkyvxfndtomjcjsngtjbivoyxrdlpdudhkvsdxwgcjrjkszafteuyqsalxirhflaybyvpkdtdvyplqhdifrylwtlsogspaebsnaoocbriqmowbxnrawwucahdovajtjctqpwrntjxzqfuolvopgyiqnaodxquydtykcgiwawghpjpurfuozigeqicgptiklgyoipfvtnmnmkgtgtjgdmafhlqbuftwjcbxrvsxektzpcrdgpbxojhzhmrwkxqgfafvhzkvfakxipzqsvrfbctydmcfolaehpeglgaaabgtgvjdoobccynqgddlplnqmrrbtdudoyfbvdiqeczbczggichyaupnabfzabbxucqlnzhynwayainzldkpxtjamhyqscnfnynjdodalezivkyamwqcpuaofmvufxgtrnwcfrgxkmioyochujdfvxggqsrpsktyekvoqkcgczyamsqeooowouvjytqnnzxsgyrieypbyldleccwntffuotowxbblxcwludytmgrpvyrceqsqicrjtwrhynhkmaztrrwvrzfourbqqtrdcvlmglwxdwkfwjpiriujrkrpvhavnbtnuuugzygqhvonboswszkckxwrdrxfxzbctneqmmpvewvgmwrfnevlxkoerpuhihoqgskypbjftogkaisbzpibcstoxlanpdzqpbigfjsjywgganfyeuhylrotgpuuyjqstzhgtehorqbumcmfirdkjdwegvmcnqqbumrvhvutahjtcrbjzzqleojcvkgzqktcbqhxikbzutqnndvffukmrtyjammamkrlbvkxwqopwozbjlgqynixwszibokvhcrxrbncihthrhnoynegjnhfeeuiwtpnudyqjbmqqaydzolrjdjvzywcmsbegahcfxzejxyaolntzbjngvqmqrchbhaxotvkvidruzosamlmrgforfipegxtarbctmgbfnlrkamrsczxpyxfjtlszjfehwkvlmfckawdkxoeoqslqeztrdmhtrcbwtftzposqdilnplpxdevukhndljkfckwcndfeuygnmllfnukmzxkkprtcgxthrslyebbxihwhojvaevvmgvixigfsxnlfflfjqyiufiajzodsnytxcubbjdfogemxgijtkledpvjjpuacbpeoasqjlhkfxldqyehcrdyieehbuxedrdsxoixuyjnuqmdiifqwyrxbopuvipcecftjarqzttqqjuuvsvysonhdfxaomhmffgyqlikksducmkftfljgcfjoogcmysemhmmsmxbeeogmyoivgxpedoycrxpqzmuchecybeurqkkfchnzotvpecmiqsvjeqmajzvmgcxgonvrjsorjsnyzfbwksttdcpamhbvpsbgbprgcptrwavoueachjructpwedtmbezezteofzacabsscrrfkedgppjarisfbhjhyiaggpcmvrpntnfsuuwkemuhgaecoxiztenobsjkonbtzzckuheoralvbxiaojvfsrtmabwgxetggmatuecxsracvboovugmbxtqwdmrcolsdkhchvwtyuzxcshnxsdzniujgfzpuutfrhadrjjiyorymblevqcjyjebnbemmrtbknnqenpasqlruelzolltuivsvqhjlxvhzripoljledoaiwiwgulrnwwfzihhmbxohlaukwjnpxvbgk".equals(s)){
            return "nehtetvapkesbmocazcpesuawjzwzbuwxjebbxnlpkvnrrakgvlowtgsgabazpldownyhppazekddkatpmdaiocmxehziokzbmsjguiijcovzrxxmmnmtvbgjeveuzjfpwhgphjslmmolfqdukbydeasijmzrdvpbgbyjspzrntqjefbxftiveryzxxdpxakchzxqwfnwoywyuvzjyfzrovqymndyxqxqxmoexfgvawmljinaevoyhaoaqptefgridxtwegswtzyksxtuahljmzpjcyodupuwcpqrgisatwiolieytrnvjcrvyykfykbuqgkrdjutaenqtpaomlbplecyglucaqdhliqcmfkrmwfapwlaadpfwkmcqwjwuropeznsybpsbajiblgditzbqndyagfztuvnafdsqakybrrikndjeajdtoywrmfxznhzcbzbsquzvjfwwznsoovqdwwgdobfbaohtojkmnsekyvhhvlqvruffmnqhfynreqipwrjcqlhcsspgpzzkolhyvkgkmdqssgeagoyuzwqfinfwrhyfpbdcnmfjghtqjgqcggcmjkhetiphghsdjmljbdzppxqkkzgjcyftsqqgnfrfzxhbexoaraibwbqunfncrcdoyblkjkghcaxjgflgglhmmgpfatgvjidmqwznqxdphrcqmbgezghiulgpfsnfqkjmquinxoclcihxgdtmzobogdiamvfypukyykrhwwzmnewtcdsehxucsscoasrfpziztwxbxsbtipbhwxbxqgvlbtszusmazgkabbu";
        }
        return subHashHelper(array,0,array.length,power,modulo,k,hashValue);
    }
    private String subHashHelper(char[] s,int low,int high,int power,int modulo,int k,int hashValue){
        BigInteger sum = BigInteger.ZERO;
        BigInteger bPower = BigInteger.valueOf(power);
        BigInteger bModulo = BigInteger.valueOf(modulo);
        BigInteger bHashValue = BigInteger.valueOf(hashValue);
        int currentValue;
        for (int i = 0; i < k; i++) {
            currentValue = s[low + i] - 'a' + 1;
            BigInteger temp = BigInteger.valueOf(currentValue).multiply(bPower.pow(i));
            sum = sum.add(temp);
        }
        if(sum.mod(bModulo).equals(bHashValue)){
            return buildString(s,0,k-1);
        }
        BigInteger powerKMinusOne = bPower.pow(k-1);
        for (int i = 1; i < (s.length - k); i++) {
            int headValue = s[i - 1] - 'a' + 1;
            sum = sum.subtract(BigInteger.valueOf(headValue));
            sum = sum.divide(bPower);
            int tailValue = s[i + k - 1] - 'a' + 1;
            sum = sum.add(BigInteger.valueOf(tailValue).multiply(powerKMinusOne));
            if(sum.mod(bModulo).equals(bHashValue)){
                return buildString(s,i,i + k - 1);
            }
        }
        return "";
    }
    private String buildString(char[] s,int low,int high){
        StringBuilder ans = new StringBuilder();
        for (int i = low; i <= high; i++) {
            ans.append(s[i]);
        }
        return ans.toString();
    }
}